#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;

// 1. 基本BFS：图的遍历
class GraphBFS {
public:
    void bfs(vector<vector<int>>& graph, int start) {
        queue<int> q;
        vector<bool> visited(graph.size(), false);
        
        q.push(start);
        visited[start] = true;
        
        cout << "BFS遍历顺序: ";
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            cout << node << " ";
            
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
};

// 2. 最短路径BFS
class ShortestPathBFS {
public:
    vector<int> shortestPath(vector<vector<int>>& graph, int start, int end) {
        queue<int> q;
        vector<bool> visited(graph.size(), false);
        vector<int> parent(graph.size(), -1);
        
        q.push(start);
        visited[start] = true;
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            if (node == end) {
                // 重构路径
                vector<int> path;
                int current = end;
                while (current != -1) {
                    path.push_back(current);
                    current = parent[current];
                }
                reverse(path.begin(), path.end());
                return path;
            }
            
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = node;
                    q.push(neighbor);
                }
            }
        }
        
        return {}; // 未找到路径
    }
};

// 3. 二叉树的层序遍历
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BinaryTreeBFS {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> level;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                level.push_back(node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            result.push_back(level);
        }
        
        return result;
    }
};

// 4. 迷宫最短路径
class MazeBFS {
public:
    int shortestPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        queue<vector<int>> q;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        q.push({start[0], start[1], 0}); // {x, y, distance}
        visited[start[0]][start[1]] = true;
        
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        while (!q.empty()) {
            int x = q.front()[0];
            int y = q.front()[1];
            int dist = q.front()[2];
            q.pop();
            
            if (x == destination[0] && y == destination[1]) {
                return dist;
            }
            
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                    maze[nx][ny] == 0 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    vector<int> next = {nx, ny, dist + 1};
                    q.push(next);
                }
            }
        }
        
        return -1; // 无法到达
    }
};

// 5. 多源BFS：腐烂的橘子
class RottingOranges {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int,int>> q;
        int fresh = 0;
        
        // 找到所有腐烂的橘子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        
        if (fresh == 0) return 0;
        
        int minutes = 0;
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        
        while (!q.empty()) {
            int size = q.size();
            bool hasRotten = false;
            
            for (int i = 0; i < size; i++) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        q.push({nx, ny});
                        fresh--;
                        hasRotten = true;
                    }
                }
            }
            
            if (hasRotten) minutes++;
        }
        
        return fresh == 0 ? minutes : -1;
    }
};

// 6. 双向BFS：单词接龙
class WordLadder {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        
        unordered_set<string> beginSet, endSet;
        beginSet.insert(beginWord);
        endSet.insert(endWord);
        
        int length = 1;
        
        while (!beginSet.empty() && !endSet.empty()) {
            if (beginSet.size() > endSet.size()) {
                swap(beginSet, endSet);
            }
            
            unordered_set<string> nextSet;
            
            for (string word : beginSet) {
                for (int i = 0; i < word.length(); i++) {
                    char original = word[i];
                    
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        
                        word[i] = c;
                        
                        if (endSet.find(word) != endSet.end()) {
                            return length + 1;
                        }
                        
                        if (wordSet.find(word) != wordSet.end()) {
                            nextSet.insert(word);
                            wordSet.erase(word);
                        }
                    }
                    
                    word[i] = original;
                }
            }
            
            beginSet = nextSet;
            length++;
        }
        
        return 0;
    }
};

// 7. 0-1 BFS：最短路径（边权为0或1）
class ZeroOneBFS {
public:
    int shortestPath(vector<vector<pair<int,int>>>& graph, int start, int end) {
        deque<int> dq;
        vector<int> dist(graph.size(), INT_MAX);
        
        dq.push_back(start);
        dist[start] = 0;
        
        while (!dq.empty()) {
            int node = dq.front();
            dq.pop_front();
            
            if (node == end) {
                return dist[node];
            }
            
            for (auto edge : graph[node]) {
                int neighbor = edge.first;
                int weight = edge.second;
                if (dist[neighbor] > dist[node] + weight) {
                    dist[neighbor] = dist[node] + weight;
                    
                    if (weight == 0) {
                        dq.push_front(neighbor);
                    } else {
                        dq.push_back(neighbor);
                    }
                }
            }
        }
        
        return -1;
    }
};

// 演示函数
void demonstrateBFS() {
    cout << "=== BFS算法演示 ===" << endl << endl;
    
    // 1. 基本图遍历
    cout << "1. 基本图遍历:" << endl;
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 5},
        {1},
        {1, 5},
        {2, 4}
    };
    GraphBFS graphBFS;
    graphBFS.bfs(graph, 0);
    cout << endl;
    
    // 2. 最短路径
    cout << "2. 最短路径:" << endl;
    ShortestPathBFS shortestPath;
    vector<int> path = shortestPath.shortestPath(graph, 0, 5);
    cout << "从节点0到节点5的最短路径: ";
    for (int node : path) {
        cout << node << " ";
    }
    cout << endl << endl;
    
    // 3. 二叉树层序遍历
    cout << "3. 二叉树层序遍历:" << endl;
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    BinaryTreeBFS treeBFS;
    vector<vector<int>> levels = treeBFS.levelOrder(root);
    cout << "层序遍历结果:" << endl;
    for (int i = 0; i < levels.size(); i++) {
        cout << "第" << i << "层: ";
        for (int val : levels[i]) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << endl;
    
    // 4. 迷宫最短路径
    cout << "4. 迷宫最短路径:" << endl;
    vector<vector<int>> maze = {
        {0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0},
        {1, 1, 0, 1, 1},
        {0, 0, 0, 0, 0}
    };
    vector<int> start = {0, 4};
    vector<int> destination = {4, 4};
    
    MazeBFS mazeBFS;
    int shortestDist = mazeBFS.shortestPath(maze, start, destination);
    cout << "迷宫最短路径距离: " << shortestDist << endl << endl;
    
    // 5. 多源BFS：腐烂的橘子
    cout << "5. 多源BFS - 腐烂的橘子:" << endl;
    vector<vector<int>> oranges = {
        {2, 1, 1},
        {1, 1, 0},
        {0, 1, 1}
    };
    RottingOranges rottingOranges;
    int minutes = rottingOranges.orangesRotting(oranges);
    cout << "所有橘子腐烂需要的时间: " << minutes << " 分钟" << endl << endl;
    
    // 6. 双向BFS：单词接龙
    cout << "6. 双向BFS - 单词接龙:" << endl;
    string beginWord = "hit";
    string endWord = "cog";
    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    
    WordLadder wordLadder;
    int ladderLength = wordLadder.ladderLength(beginWord, endWord, wordList);
    cout << "从 \"" << beginWord << "\" 到 \"" << endWord << "\" 的最短转换序列长度: " << ladderLength << endl << endl;
    
    // 7. 0-1 BFS
    cout << "7. 0-1 BFS - 最短路径:" << endl;
    vector<vector<pair<int,int>>> weightedGraph = {
        {{1, 0}, {2, 1}},
        {{0, 0}, {3, 1}},
        {{0, 1}, {3, 0}},
        {{1, 1}, {2, 0}}
    };
    
    ZeroOneBFS zeroOneBFS;
    int shortestWeightedDist = zeroOneBFS.shortestPath(weightedGraph, 0, 3);
    cout << "从节点0到节点3的最短路径距离: " << shortestWeightedDist << endl;
}

int main() {
    demonstrateBFS();
    return 0;
}
